package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author qidi
 * @date 2022-01-06 16:56:31
 */
class Q0113_PathSumIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<Integer>> result = null;
        LinkedList<Integer> cur = null;

        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            result = new ArrayList<>();
            if (root == null) return result;

            cur = new LinkedList<>();
            process(root, targetSum);

            return result;
        }

        private void process(TreeNode node, int sum) {
            if (node == null) return;
            if (node.left == null && node.right == null) {
                if (node.val == sum) {
                    cur.add(node.val);
                    result.add(new ArrayList<>(cur));
                    cur.removeLast();
                }
                return;
            }

            cur.add(node.val);
            process(node.left, sum - node.val);
            process(node.right, sum - node.val);
            cur.removeLast();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0113_PathSumIi().new Solution();
        BTreeUtil util = BTreeUtil.getInstance();
        System.out.println(solution.pathSum(util.generateFromArray(5, 4, 8, 11, null, 9, 4, 7, 2, null, null, 5, 1), 22));
        System.out.println(solution.pathSum(util.generateFromArray(1, 2, 3), 5));
        System.out.println(solution.pathSum(util.generateFromArray(1, 2), 0));
    }
}